package com.LeeCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 从先序遍历还原二叉树
 */

public class Code1028 {
    public static void main(String[] args) {
        String s = "1-2--3--4-5--6--7";
        new Code1028().recoverFromPreorder(s);
    }

    public TreeNode recoverFromPreorder(String traversal) {
        char[] chars = traversal.toCharArray();

        Deque<TreeNode> stack = new LinkedList<>();
        int index = 0, n = chars.length;
        while (index < n) {
            int level = 0;
            while (index < n && chars[index] == '-') {
                index++;
                level++;
            }

            int val = 0;
            while (index < n && chars[index] != '-') {
                val = val * 10 + chars[index++] - '0';
            }
            TreeNode node = new TreeNode(val);
            if (level == stack.size()) {
                if (!stack.isEmpty()) {
                    stack.peek().left = node;
                }
            } else {
                while (level < stack.size()) {
                    stack.pop();
                }
                stack.peek().right = node;
            }
            stack.push(node);
        }
        while (stack.size() > 1) {
            stack.pop();
        }
        return stack.peek();
    }
}
